---
title: "7、砝码称重"
created: 2025-11-28
tags:
  - 算法
---

# 7、砝码称重

## 题目 [砝码称重](https://www.lanqiao.cn/paper/3829/problem/1447/)

![[image-0c731a1e.png]]

## 思路分析

![[image-0d07e1e9.png]]

![[image-0d07e1e9.png]]

状态表示 从前i个砝码里面选 选到总重量恰好为j的所有选法的数量（只需要看有没有 count可以转变成bool)

状态计算 不选的话 就是f[i-1][j]的状态 选的话 有两种可能 如果在左边 就是加上这个砝码后重量才达到j 所以状态应该是从f[i-1][j-w[i]]转移而来
如果加在右边 那就是减去这个砝码（加上这个负砝码）后才达到j重量 所以状态从f[i-1][j+w[i]]转移而来

再考虑初始化 0个砝码里选出重量为0合法 1~n个砝码中选出重量0 好像也合法 因为可以什么都不选 那就全初始化成1

最后的答案就是 遍历f[n][1-M] 看有多少个不为0

另外一个点就是 左边6 右边2量出来的4 和 左边2 右边6量出来的-4是一样的 都是4这个重量 所以可以加绝对值

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=110,M=2e5+10;

int f[N][M]; //1-M个物品中选(最多100个物品) 体积恰好为1-M(M最大为1e5 因为有两边 所以开双倍)

int w[N];//每个物品的价值

int n,m;

int main()

{

	cin>>n;

	for(int i=1;i<=n;i++){

		cin>>w[i];

		m+=w[i];//能称出的最大重量肯定是所有之和

	}

	for(int i=0;i<=n;i++)

		f[i][0]=1;//什么都不选也是一种选法

	for(int i=1;i<=n;i++){//枚举砝码

		for(int j=0;j<=m;j++){//枚举重量

			f[i][j]=f[i-1][j]+f[i-1][abs(j-w[i])]+f[i-1][j+w[i]];

		}

	}

	int ans=0;

	for(int i=1;i<=m;i++)

		if(f[n][i])

			ans++;

	cout<<ans;

	return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[6、时间显示|6、时间显示]] 🏠 [[00-刷题理模型]] ➡️ [[8、杨辉三角形|8、杨辉三角形]]